package tree

import (
	"fmt"
)

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func LevelOrder(tree *TreeNode) {
	var queue []TreeNode
	queue = append(queue, *tree)
	for len(queue) != 0 {
		floorWidth := len(queue)
		for i := 0; i < floorWidth; i++ {
			node := queue[0]
			fmt.Printf("node.Val: %v", node.Val)
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, *node.Left)
			}
			if node.Right != nil {
				queue = append(queue, *node.Right)
			}
		}
		fmt.Println()
	}
}

func levelOrder(root *TreeNode) [][]int {
	var queue []TreeNode
	var res [][]int
	if root != nil {
		queue = append(queue, *root)
	}
	for len(queue) != 0 {
		floorWidth := len(queue)
		var list []int
		for i := 0; i < floorWidth; i++ {
			node := queue[0]
			list = append(list, node.Val)
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, *node.Left)
			}
			if node.Right != nil {
				queue = append(queue, *node.Right)
			}
		}
		res = append(res, list)
	}
	return res
}

func preorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Printf("root.Val: %v\n", root.Val)
	preorderTraversal(root.Left)
	preorderTraversal(root.Right)
}

func inorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	inorderTraversal(root.Left)
	fmt.Printf("root.Val: %v\n", root.Val)
	inorderTraversal(root.Right)
}

func postorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	postorderTraversal(root.Left)
	postorderTraversal(root.Right)
	fmt.Printf("root.Val: %v\n", root.Val)
}

func preorderTraversal2(root *TreeNode) []int {
	stack := []TreeNode{}
	ans := []int{}
	for root != nil || len(stack) != 0 {
		for root != nil {
			ans = append(ans, root.Val)
			stack = append(stack, *root)
			root = root.Left
		}
		root = stack[len(stack)-1].Right
		stack = stack[:len(stack)-1]
	}
	return ans
}

func inorderTraversal2(root *TreeNode) []int {
	stack, ans := []TreeNode{}, []int{}
	for root != nil || len(stack) != 0 {
		for root != nil {
			stack = append(stack, *root)
			root = root.Left
		}
		root = &stack[len(stack)-1]
		ans = append(ans, root.Val)
		root = root.Right
		stack = stack[:len(stack)-1]
	}
	return ans
}

func postorderTraversal2(root *TreeNode) []int {
	stack, ans := []*TreeNode{}, []int{}
	lastNode := &TreeNode{Val: 0}
	for root != nil || len(stack) != 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		node := stack[len(stack)-1]
		prev := node.Right
		if prev == lastNode || node.Right == nil {
			stack = stack[:len(stack)-1]
			ans = append(ans, node.Val)
			lastNode = node
		} else {
			root = node.Right
		}
	}
	return ans
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p != nil && q != nil && p.Val == q.Val {
		return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
	} else {
		return false
	}
}

func isSymmetric(root *TreeNode) bool {
	return isOppositeTree(root.Left, root.Right)
}

func isOppositeTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p != nil && q != nil && p.Val == q.Val {
		return isSameTree(p.Left, q.Right) && isSameTree(p.Right, q.Left)
	} else {
		return false
	}
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
	return root
}

func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	if root.Left == nil && root.Right == nil && root.Val == targetSum {
		return true
	}

	return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

// 最小深度
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var deepLeft, deepRight int = minDepth(root.Left), minDepth(root.Right)

	if root.Left == nil {
		deepLeft = deepRight
	}

	if root.Right == nil {
		deepRight = deepLeft
	}
	return min(deepLeft, deepRight) + 1
}

func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
		return root.Left.Val + sumOfLeftLeaves(root.Right)
	}
	return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}

// 锯齿形层序遍历
func zigzagLevelOrder(root *TreeNode) [][]int {
	ans := make([][]int, 0)

	if root == nil {
		return ans
	}
	queue := make([]*TreeNode, 0)

	floor := 0
	queue = append(queue, root)
	for len(queue) != 0 {
		floor++
		n := len(queue)

		arr := make([]int, 0)
		for i := 0; i < n; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			arr = append(arr, node.Val)
		}
		if floor%2 == 0 {
			n = len(arr) - 1
			for i := 0; i <= n/2; i++ {
				arr[i], arr[n-i] = arr[n-i], arr[i]
			}
		}
		ans = append(ans, append([]int{}, arr...))
	}
	return ans
}
